package graph;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName DepthFirstSearch.java
 * @Description TODO
 * @createTime 2020年09月01日 20:21:00
 */
public class DepthFirstSearch {
	//索引代表顶点，值表示当前顶点是否已经被搜索
	private boolean[] marked;
	//记录有多少个顶点与s顶点相同
	private int count;

	//构造深度优先搜索对象，使用深度优先搜索找出g图中s顶点的所有相邻顶点
	public DepthFirstSearch(Graph graph, int s) {
		// 初始化marked数组
		this.marked = marked;
		// 初始化跟顶点s相通的顶点的数量
		this.count = count;

		dfs(graph,s);
	}

	//使用深度优先搜索找出graph图中v顶点的所有相通顶点
	private void dfs(Graph graph,int v){
		//把v顶点标记为已搜索
		marked[v]=true;

		//遍历v的子节点
		for (Integer w : graph.adj(v)) {
			//如果v的子节点标记过了，就找v的子节点的兄弟节点
			if (!marked[w]){
				dfs(graph,w);
			}
		}
		count++;
	}

	//判断w订单与s顶点是否相通
	public boolean marked(int w){
		return marked[w];
	}

	//获取与顶点s相通的所有顶点的总数
	public int count(){
		return count;
	}
}
